Image quality assessment and adjustment is often done in an image processing system (such as a photocopier, electronic scanner, digital camera, or video camera) by capturing the image of a test target with known physical attributes. The measured attributes are compared to the physical measurements to provide a characterization of the system. For example, a sequence of gray patches, increasing from light to dark (called a step-wedge) can be produced with known darknesses (optical densities) by measuring the ratio of impinging light to the amount of reflected light under controlled conditions. The step-wedge is then captured with an electronic imaging device so that the image is represented as an array of pixel values. Each patch represents a different optical density and maps to a "digital count" in the imaging device. A mapping can thus be inferred from true optical density to digital counts in the electronic device. This mapping, called a tone reproduction curve (TRC), is a calibration of the device. With the TRC, one may use the electronic device as a measurement instrument, or use the TRC to correct defects in the tone of subsequent images captured using the device. An automatic means of detecting the location of patches in the array of pixels in electronic device (or computer memory) is needed to conveniently compute the mapping.
One method is to put distinguishing markers in the corners of the test target and measure the positions of the patches relative to the markers. A calibration program as executed by a central processing unit would analyze the array to detect the markers. By knowing the physical distance among the markers and computing the distance between the detected markers in the image, a scale factor can be computed which allows the positions of the patches in the array to be computed.
Automatic calibration is desirable in a commercial product where the naive user is relieved of the task of calibration. Indeed, a set of instructions can be provided to the user to image a test target and press a button and then continue with image capture.
In a document scanning scenario, good image quality is achieved by characterizing many aspects of the device, including its inherent resolution (smallest image features that can be preserved through the system). Systematic or random distortions may be introduced by the scanner. Proper characterizations of these distortions allows compensation for these distortions via image processing algorithms executed in hardware or software. There often are image processing functions used by the device to increase image quality when printed. For example, a scanned document may be "halftoned" to represent gray by a cluster of black dots. The arrangement of black dots, carefully-crafted to represent gray unobtrusively to the human visual system, may be ruined by scanning and printing. To compensate for this after scanning, image processing algorithms, modeling the human visual system, estimate the gray that a human was intended to perceive. Printing the gray produces significantly better reproduction. To test the quality of this reproduction, the entire test target is rendered, printed in halftones and scanned in. Measurements from original patches are compared with scanned halftoned patches. To make this process automatic for a naive user, the registration markers must be detected even though they have suffered serious degradation through scanning, halftoning, printing and rescanning.
Many other measurements are possible depending on the imaging system. FIG. 2 shows an example of a test target. There are numerous patches to measure many characteristics of the imaging system. The two markers at the top are to be detected. Calibration algorithms use the detected positions to then compute the positions of the patches in the image array. The same test target may be scanned in a plurality of resolutions, including anisotropic aspect ratios (e.g. 400 by 600 dots per inch), as well as being subject to extreme distortions by the imaging system. Thus an algorithm to detect the markers must be robust against these distortions (halftoning, low contrast, etc). The present invention is designed and proven to be robust against a variety of distortions.
U.S. Pat. No. 5,198,907 provides a means for target registration using an inverted `L`-shaped figure, called "guide bars". Guide bars are detected using edge detection and following. The algorithm starts at the upper left corner and uses differences in "exposure" to detect the edge. It then follows edges to find bars with the correct width and height. The guide bars are long relative to the captured area and in horizontal and vertical directions. The dimensions (lengths and widths) must be known beforehand to allow detection. These constraints preclude marker identification under the extreme distortions this invention overcomes.
U.S. Pat. No. 5,642,202 provides a means for calibrating a printer. Using registration marks, the original and scanned, printed version can be registered and compared to generate calibration data. Registration marks are three collinear triangles having designated non-collinear "apexes" at known positions which are used to compute the registration transformation from the scanned image to the original. These triangles are detected using black-to-white and white-to-black transitions along horizontal scans. This method is not robust to halftoning (dithering or error diffusion) nor can there can be any image content or noise between the triangles because the algorithm looks for exactly 6 transitions. Nor can there be large amounts of document skew that would make it impossible to find the six transitions.
Other pattern detection methods are presented by the following patents:
U.S. Pat. No. 4,153,897 Yasuda, et. al.
Issued May 8, 1979 U.S. Pat. No. 5,216,724 Suzuki, et. al.
Issued June 1, 1993 U.S. Pat. No. 5,291,243 Heckman, et. al.
Issued March 1, 1994
Yasuda et al. discloses a pattern recognition system where similarities between unknown and standard patterns are identified. Similarities are detected at first in respective shifting conditions where the unknown and standard patterns are relatively shifted from each other over the first limited extent, including the condition without shift. The maximum value of these similarities is then detected. The similarities are further detected in respective shifting conditions where the unknown and standard patterns are relatively shifted from each other over the second extent larger than the first limited extent, when the shifting condition which gave the maximum value is that without relative shift.
Suzuki et al. discloses an apparatus for image reading or processing that can precisely identify a particular pattern, such as bank notes or securities. A detecting unit detects positional information of an original image and a discriminating unit extracts pattern data from a certain part of the original image to discriminate whether the original image is the predetermined image based on the similarity between the pattern data and the predetermined pattern.
Heckman et al. discloses a system for printing security documents which have copy detection or tamper resistance in plural colors with a single pass electronic printer. A validating signature has two intermixed color halftone patterns with halftone density gradients varying across the signature in opposite directions, but different from the background.
A publication by Pal et al. entitled "A review of image segmentation techniques," Pattern Recognition, Vol 26, No 9, p 1277-1294 (1993) also discloses several image segmentation techniques.
All of the references cited herein are incorporated by reference for their teachings.